package backtracing;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: june
 * @date: 2023/8/1
 * @description: 78. 子集
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 **/

public class Subsets_78 {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> subset = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        backtrace(nums, 0);
        return result;
    }

    private void backtrace(int[] nums, int startIndex) {
        // 每一次遍历的都是子集，都可以添加到结果中，并且也不用剪枝
        result.add(new ArrayList<>(subset));
        if (startIndex >= nums.length) {
            return;
        }

        for (int i = startIndex; i < nums.length; i++) {
            subset.add(nums[i]);
            // 如果在这里添加元素，则不会包含空集
//            result.add(new ArrayList<>(subset));
            backtrace(nums, i + 1);
            subset.remove(subset.size() - 1);
        }
    }

    public static void main(String[] args) {
        Subsets_78 subsets_78 = new Subsets_78();
        int[] nums = {1, 2, 3};
        List<List<Integer>> ss = subsets_78.subsets(nums);
        System.out.println(ss);
    }
}
